Basic Theory of Optimization Algorithms

凸集

凸集的几何定义 在空间中, 经过不同的两点可以确定一条直线, 其方程为

特别, 当时, 直线退化为以为端点的线段。

如果过集合中的任意两点的直线都在内, 则称为仿射集, 即

可以证明，线性方程组的解集是仿射集；反之，任何仿射集均可表示为某一线性方程组的解集。

如果连接集合中的任意两点的线段都在内, 则称为凸集, 即

显然仿射集都是凸集。

凸集具有以下性质:

1. 若是凸集, 则是凸集.
2. 若和均是凸集, 则是凸集.
3. 若和均是凸集, 则是凸集，进而，任意多凸集的交都是凸集.
4. 凸集的内部和闭包都是凸集.

从凸集中可以引出凸组合和凸包的概念：

1. 凸组合：设是一个非空集合，，且，则称为的凸组合.
2. 凸包：设是一个非空集合，，则称的凸包为所有的凸组合所构成的集合，即
   

可以证明若，则是凸集；反之亦然。事实上，是包含的最小凸集，也即是包含的所有凸集的交集。

仿射集和凸集的定义很像, 除了的范围有所不同。 受此启发, 从凸组合和凸包的定义中可以自然引出仿射组合和仿射包的概念。

1. 仿射组合：设是一个非空集合，，且，则称为的仿射组合.
2. 仿射包：设是一个非空集合，，则称的仿射包为所有的仿射组合所构成的集合，即
   

与凸包类似，的仿射包是包含的最小仿射集。

锥组合和凸锥

1. 锥：我们称集合是一个锥，如果对于任意，有。 如果是凸集，那么称其是凸锥。
2. 锥组合：设是一个非空集合，，，则称为的锥组合.

等价地，若集合中任意点的锥组合都在中, 则是凸锥。

常见凸集

1. 超平面：任取非零向量，形如
   
   的集合称为超平面。
2. 半空间：任取非零向量，形如
   
   的集合称为半空间。超平面是仿射集和凸集, 半空间是凸集但不是仿射集。
3. 多面体：把满足线性等式和不等式组的点的集合称为多面体, 即
   
   其中是的矩阵，，是的矩阵，。多面体是有限个半空间和超平面的交, 因此由凸集的性质可知, 其为凸集。
4. 范数球：设空间中到某一定点(称为中心)的距离小于等于定值(称为半径)的点的集合为(范数)球, 即
   
5. 椭球：形如
   
   的集合为椭球, 其中为椭球中心, 对称正定, 且非奇异。
6. 范数锥： 形如
   
   的集合称为范数锥。锥是凸集, 但不是仿射集。

保凸运算

1. 仿射变换：设是仿射变换（包括缩放、平移、投影等），即
   
   其中，，则凸集在下的像是凸集，且凸集在下的原像也是凸集。
2. 透视变换：设为
   
   是透视变换，则凸集在下的像和原像都是凸集。
3. 分式线性变换：设为
   
   是分式线性变换，则凸集在下的像和原像都是凸集。

广义不等式与对偶锥

如果凸锥满足

• 是闭的；
• 是实心的，即；
• 是尖的，即内部没有直线：若，，则；

那么称是一个适当锥 (proper cone)。

常见的适当锥包括非负卦限，半正定锥，上的有限非负多项式空间

等。

给定适当锥之后，可以定义一种偏序关系：

类似的严格偏序关系为

这样的偏序关系称为广义不等式 (generalized inequality)，注意这样的偏序关系不保证所有对象都具有可比较性。

广义不等式具有以下性质：

1. 自反：；
2. 反对称：；
3. 传递：；
4. 可加：；
5. 非负缩放：；

设是全空间中一个锥，则的对偶锥为

对偶锥是相对于锥定义的, 因此我们知道锥的同时也可以求出对偶锥。将对偶锥为自身的锥称为自对偶锥。

对偶锥具有以下性质：

1. 是锥，即使不是锥也同样如此；
2. 是闭凸集；
3. 若，则是尖的，即内部不含直线；
4. 若的闭包是尖的，则；
5. 若是适当锥，则也是适当锥；
6. 二次对偶：是的凸包的闭包。特别地，当是闭凸锥时，。

既然适当锥的对偶锥仍是适当锥, 则可以用适当锥的对偶锥也可以诱导广义不等式

我们在下文简称其为”对偶广义不等式”，满足如下性质：

1. 对于任意都成立；
2. 对于任意都成立。

使用对偶广义不等式的好处是, 对偶锥始终是闭且凸的, 并可将一个偏序问题转换为满足一个偏序条件的全序问题。

分离超平面定理

超平面是空间中一类特殊的凸集(仿射集), 可以证明空间中的超平面恰好是维的。我们可以用超平面分离不相交的凸集。

Hyperplane Separation Theorem

如果和是中的两个互不相交的非空凸集，则存在非零向量和标量，使得 即超平面将和分隔到两个不同的半空间中。

超平面分离定理表明, 如果要软划分中的2个凸集, 则只需要求得一个适当的超平面即可。这在分类问题中属于很容易解决的问题。实际上, 如果有任何一个集合不是凸集, 则定理一般不成立, 此时我们若要划分不同的集合, 则一般需要使用更加复杂的平面。

我们在超平面分离时提到了软划分的概念, 其表明若集合仅是凸集, 则定理中等号可能成立, 即某一凸集与超平面相交。很多时候进一步要求超平面与任何凸集都不交, 为此我们需要加强定理的条件.

Strict Hyperplane Separation Theorem

如果和是中的两个互不相交的非空凸集，且是闭集，是紧集，则存在非零向量和标量，使得 即超平面将和严格分隔到两个不同的半空间中。

此定理的退化形式即退化为单点集，此时需要。当恰好落在的边界上时(此时不满足”不相交”的条件), 我们可以构造支撑超平面：

支撑超平面 给定集合以及边界上的点，如果满足，则称集合

为在处的支撑超平面。

根据以上定义，点与被分开。从集合上而言，超平面与集合在处相切，且半空间包含。

根据凸集成立的分离超平面定理, 凸集上任何的边界点都满足支撑超平面存在的条件, 则对于凸集成立如下的定理：

Supporting Hyperplane Theorem

若是中的一个非空凸集，则的任意边界点都存在支撑超平面。

凸函数

基础定义

矩阵内积 定义矩阵和的内积为

根据Cauchy不等式可知

其中是矩阵的Frobenius范数。

矩阵变量函数的导数 多元函数梯度的定义可以推广到变量是矩阵的情形．对于以矩阵为自变量的函数，若存在矩阵满足

其中是一个的矩阵，是矩阵和的内积，则称在处Fréchet可微，称为在处的Fréchet意义下的梯度。可以证明矩阵变量函数的梯度为

其中为关于的偏导数。

在实际应用中，矩阵Fréchet可微的定义和使用往往比较繁琐，为此我们需要介绍另一种定义 — Gâteaux可微。对于矩阵变量函数，如果存在矩阵使得

则称在处Gâteaux可微，称为在处的Gâteaux意义下的梯度。可以证明，当是Fréchet可微函数时，也是Gâteaux可微的，且这两种意义下的梯度相等。

Example. 现在给出几种常见的矩阵变量函数的Gâteaux梯度：

1. 线性函数，对于任意的有
   
   因此。
2. 二次函数，注意到
   
   因此
   
   类似地可得
   
3. ln-det函数，其中，给定，对于任意的以及都有
   
   因为，因此可被合同对角化，设它的特征值为，则
   
   因此。

广义实值函数与适当函数 令为广义实数空间，称映射为广义实值函数。

给定广义实值函数与非空集合，如果

1. 存在使得;
2. 对于任意的都有；

则称函数关于集合是适当的。概括来说，适当函数的特点是“至少有一处取值不为正无穷”，以及“处处取值不为负无穷”。

下水平集与上方图 对于广义实值函数而言，定义的-下水平集为

定义的上方图为

闭函数 设是一个广义实值函数，当上方图是闭集时，称是一个闭函数。

回忆对于广义实值函数而言，如果对于任意的都有

则是下半连续函数。

事实上，闭函数的定义等价于要求下半连续 — 设是一个广义适当（保证下水平集定义有意义）实值函数，则以下命题等价：

1. 的任意-下水平集都是闭集；
2. 是下半连续的；
3. 是闭函数。

闭（下半连续）函数间的简单运算会保持原有性质:

• 加法: 若与均为适当的闭（下半连续）函数，并且，则也是闭（下半连续）函数．其中适当函数的条件是为了避免出现未定式的情况；
• 仿射映射的复合: 若为闭（下半连续）函数, 则也为闭（下半连续）函数；
• 取上确界: 若每一个函数均为闭（下半连续）函数，则也为闭（下半连续）函数。

凸函数 给定适当函数，如果满足

1. 是凸集；
2. 对于任意的和都有
   

则称是凸函数。若是凸函数，则称是凹函数。当上述不等式总是严格成立时，称是严格凸函数。

常见的凸函数包括：仿射函数，指数函数，幂函数，绝对值的幂，负熵（定义域为）；更一般地，在高维空间中的仿射函数，各种范数也都是凸函数。其中仿射函数既是凸函数也是凹函数。

强凸函数 若存在使得

是凸函数，则称是-强凸函数，其中是强凸参数。借助凸函数的定义可知该要求等价于

对任意的和都成立。

凸函数的判定

1. 降维 最简单的判定一个函数是否为凸函数的方法是将函数限制在任意直线上，然后判断对应的一维函数是否是凸的：是凸函数当且仅当对于任意的和，函数是关于的凸函数，其中
   

2. 考察上方图 另外，也可以借助上方图来进行判定：函数为凸函数当且仅当其上方图是凸集。

3. 凸性的一阶条件 对于定义在凸集上的可微函数，是凸函数当且仅当
   
   对于任意的都成立。

4. 梯度单调性 设为可微函数，则为凸函数当且仅当为凸集且为单调映射，即
   
   对于任意的都成立。

5. 凸性的二阶条件 设为定义在凸集上的二阶连续可微函数，则

   • 是凸函数当且仅当
     
   • 如果对于任意的都成立，则是严格凸函数。

对于可微函数而言，上述二阶条件通常可以很方便地判定它是否是凸函数。

Example. 下面使用二阶条件考虑几个经典的凸函数：

1. 最小二乘函数，因为
   
   因此对于任意，都是凸函数。
2. quadratic-over-linear函数，直接计算可知
   
   因此是上的凸函数。
3. log-sum-exp函数，同样直接计算可知
   
   其中。为了说明，只需证明对于任意都有
   
   也即
   
   由Cauchy不等式可知
   
   因此是凸函数。
4. 几何平均函数是上的凹函数。
5. ln-det函数在是凸函数。任取和，将限制在上，要求使得，则
   
   其中是的第个特征值。由于
   
   因此关于是凸函数，又由第一条判定定理可知是凸函数。

保凸运算

除了利用上一小节中的判定定理来判断一个函数是否是凸函数，也可以通过说明该函数可由简单的凸函数通过一些保凸的运算得到，这些保凸的运算包括：

1. 非负加权和：

   1. 若是凸函数，则是凸函数，其中；
   2. 若都是凸函数，则也是凸函数；

   例子：线性不等式的对数障碍函数
   

2. 与仿射函数的复合：若是凸函数，则也是凸函数；

   例子：仿射函数的任意范数。

3. 逐点取极大值：若是凸函数，则是凸函数。

   例子：

   • 分段线性函数；
   • 的前个最大分量之和
     

4. 逐点取上界：若对每个而言，是关于是凸函数，则
   
   是凸函数；

   例子：

   • 集合的支撑函数；
   • 集合到给定点的最远距离；
   • 对称矩阵的最大特征值。

5. 与标量函数的复合：给定函数和，定义。如果的定义域非全空间，则对于定义的延拓，令，则

   1. 是凸函数，是凸函数且单调不减时，或者
   2. 是凹函数，是凸函数且单调不增时，
      得到的是凸函数。

   例子：

   • 如果是凸函数，则是凸函数；
   • 如果是正值凹函数，则是凸函数。

6. 与向量函数的复合：给定函数和，定义
   
   如果的定义域非全空间，则对于定义的延拓，令，则

   1. 都是凸函数，是凸函数且单调不减时，或者
   2. 都是凹函数，是凸函数且单调不增时，
      得到的是凸函数。

   例子：

   • 如果是凸函数，则是凸函数；
   • 如果是正值凹函数，则是凹函数。

7. 取下确界：若关于整体是凸函数，是凸集，则
   
   是凸函数。

   例子：

   • 函数在满足与的情况下是凸函数，关于取最小值可得
     
     是凸函数。进一步地，的Schur补；
   • 点到凸集的距离是凸函数。

8. 透视函数：定义的透视函数为
   
   若是凸函数，则是凸函数。

   例子：

   • 是凸函数，因此是区域上的凸函数；
   • 是凸函数，因此相对熵函数是上的凸函数；
   • 若是凸函数，则
     
     是区域上的凸函数。

9. 共轭函数：适当函数的共轭函数定义为
   
   无论原函数是否为凸函数，共轭函数恒为凸函数。
   例子：

• 负对数，注意到
  
• 强凸二次函数，其中，的对偶函数为
  

典型优化问题

回顾最优化问题的一般形式为

按照目标和约束函数的简易程度分，可以分为线性规划和非线性规划．线性规划是指所有的目标函数和约束函数都是线性的，非线性规划是指目标函数和约束函数中至少有一个是非线性的。

另外也可按照问题最优解的性质，分为凸优化问题与非凸优化问题．凸优化问题的任何稳定点都是全局极小点，非凸优化问题的稳定点则可能是局部极小点，全局极小点甚至是鞍点。

凸优化

标准形式的凸优化问题为

其中都是凸函数，等式约束均是线性约束。凸优化问题最重要的性质是：凸问题的可行集是凸集。

值得注意的是，优化问题性质和其定义的形式有关，例如

并不是凸优化问题，因为非凸，且不是线性函数，但是它等价于如下凸优化问题：

凸优化问题的最大优势在于其任意局部极小点都是全局最小点。

线性规划

线性规划问题的一般形式为

其中，，，，，是决策变量。

在实际中，由于其他形式都可进行转化，故考虑上述问题的两种特殊形式：

1. 标准形式：
   
2. 不等式形式：
   

Example：基追踪问题 基追踪问题是压缩感知中的一个基本问题，可以写为

通过对每个引入一个新的变量可以将原问题转化为

这正是一个线性规划问题。除此之外，也可以引入的正部和负部，其中

利用以及，原问题可以转化为

这同样是一个线性规划问题。

此外，常见的线性规划问题还包括：运输问题、数据拟合、计算多面体的Chebyshev中心以及分式线性问题等。

二次锥规划

二次规划问题的一般形式为

其中。上述问题对应于在一个多面体内最小化一个二次凸问题。

常见的二次规划问题包括：

1. 最小二乘：
   
2. 随机线性规划：
   

更一般地，带有二次约束的二次规划问题 (QCQP) 形如

其中，即目标函数与约束均为二次凸的。当时，上述问题的可行域为个椭球与一个仿射集的交集。

事实上，凸问题中的不等式约束可以使用广义不等式来代替得到更一般的形式：

其中是凸函数，关于适当锥是-凸的。这样的广义凸问题与标准凸问题有相同的性质。

当目标函数和约束条件都为仿射函数时，上述问题称为锥规划问题：

也可以将线性规划问题延伸到了非多面体锥上。

现在定义二次锥 (SOC)为

在此基础上定义旋转二次锥为

它等价于对二次锥中的做变换，其中

即将在平面中绕原点旋转度。

二次锥规划 (SOCP) 的一般形式为

其中不等式约束构建了更一般的二次锥约束，即

其中是某个二次锥。

对于, 问题退化为LP; 所以，SOCP问题形式比LP更常规。若, 问题退化为QCQP。我们将看到，LP和QCQP也能转化为SOCP问题。

Remark. 若是将SOCP的约束两边平方，得到的可能非凸，故这样的转换不等价，为了保证等价性需要再加上。例如等价于且。

LP转化为SOCP 对于线性规划的不等式约束，可以将它改写为

其中，于是线性约束可转化为二次锥约束。

QP转化为SOCP 对于二次规划问题

其中，，目标函数可以写为

其中，等价的SOCP问题形式为

QCQP转化为SOCP 对于QCQP问题

等价于二次锥约束

其中

Examples

1. 最小范数问题：令，则
   1. 等价于
      
   2. 等价于
      
2. 极小化仿射函数的调和平均值
   
   等价于
   

半定规划

半定规划（SDP）是线性规划在矩阵空间中的一种推广．它的目标函数和等式约束均为关于矩阵的线性函数，而它与线性规划不同的地方是其自变量取值于半正定矩阵空间。

半定规划问题的一般形式如下：

其中，，为已知向量和矩阵，是决策变量。若上式中都是对角矩阵，那么约束即为线性规划约束。

类似于线性规划问题，半正定规划的标准形式为

与之对应的对偶形式为

由于许多非凸问题松弛为半定规划后，得到的近似问题比线性规划更紧，所以半定规划更普遍。

LP转化为SDP 对于线性规划问题

其中的约束条件等价于

其中

因此对应的SDP形式为

SOCP转化为SDP 首先回忆Schur引理：对于分块矩阵

如果，则当且仅当的Schur补。于是SOCP问题

等价于如下SDP问题

非凸QCQP的半定规划松弛 考虑二次约束二次规划问题

其中为对称矩阵。当部分为对称不定矩阵时，上述问题是NP 难的非凸优化问题。注意到对于任意的和都有

因此上述原问题中的所有的二次项均有如下等价刻画

于是原问题等价于

现在进一步定义满足

下面将上述等价问题松弛为半定规划问题。在上述问题中唯一的非线性部分为约束，可以将它松弛为半正定约束

可以证明等价于，于是原问题的半正定松弛为

最优性理论

本节考虑优化问题

其中是问题的可行域。

下面首先考虑最优解的存在性, 然后考虑如何求出其最优解。

解的存在性

在分析中的Weierstrass定理表明定义在紧集上的连续函数一定存在最大(最小) 值点，然而在许多实际问题中, 定义域可能不是紧的, 目标函数也不一定连续, 因此需要将此定理推广来保证最优化问题解的存在性。

Generalized Weierstrass's Theorem

如果适当且闭，且以下条件中的任意一个成立：

1. 有界；
2. 存在常数使得下水平集 非空且有界；
3. 是强制的，即对于任意满足的点列都有

则函数的最小值点集非空且紧。

Remark. 上述定理的三个条件在本质上都是保证的最小值不能在无穷远处取到，因此我们可以仅在一个有界的下水平集中考虑的最小值。另外，由于定理仅要求为适当且闭的函数, 并不需要的连续性, 因此比通常的Weierstrass定理应用范围更广。

尽管推广的Weierstrass定理给出了最优解的存在性条件, 但其对应的解可能不止一个。当最优解是唯一存在时, 我们可以通过比较不同算法收敛至该解的速度来判断算法好坏。但是如果问题有多个最优值点, 不同的算法收敛到的最优值点可能不同, 那么这些算法收敛速度的比较就失去了参考价值。因此, 最优化问题解的唯一性在理论分析和算法比较中扮演着重要角色。

拟强凸函数 给定凸集和。如果任取以及都有

则称函数是拟强凸的。

Remark. 拟强凸函数的性质与凸函数类似但不相同：

1. 强拟凸函数不一定是凸函数, 但其任意一个下水平集都是凸集, 并可以包含一部分性质较好的非凸函数。
2. 任意强凸函数均为强拟凸的, 但凸函数并不一定是强拟凸的。
3. 任何定义在闭有界凸集上的强凸函数，如，的最优解都是唯一存在的。
4. 对于一般的凸函数, 其最优解可能不唯一, 比如, 任意都是的最优解。

我们将上述第三条注记严格化为如下唯一性定理：

Uniqueness (Strongly quasi-convex function)

设是一个非空紧凸集，如果是适当、闭且拟强凸函数，则存在唯一的使得

无约束可微问题

无约束可微优化问题通常表示为如下形式：

其中是连续可微函数。

给定一个点, 我们想要知道这个点是否是函数的一个局部极小解或者全局极小解。如果从定义出发, 需要对其邻域内的所有点进行判断, 这不可行，因此，需要一个更简单的方式来验证一个点是否为极小值点。我们称其为最优性条件，它主要包含一阶最优性条件和二阶最优性条件。

下降方向 对于可微函数和点，如果存在向量使得

则称是在处的一个下降方向。

由下降方向的定义, 容易验证: 如果在点处存在一个下降方向, 那么对于任意的, 存在, 使得

因此在局部最优点处不能有下降方向。这给出了局部最优点的一阶必要条件：

First Order Necessary Condition

设在内可微。如果是一个局部极小点，则

在没有额外假设时, 如果一阶必要条件满足, 我们仍然不能确定当前点是否是一个局部极小点。假设在点的一个开邻域内是二阶连续可微的。类似于一阶必要条件的推导, 可以借助当前点处的二阶泰勒展开来逼近该函数在该点附近的取值情况, 从而来判断最优性：在附近对进行Taylor展开可得

当一阶必要条件满足时上式变为

于是可得二阶最优性条件：

Second Order Optimal Condition

设在内二阶可微。则以下命题成立：

1. 必要条件： 如果是一个局部极小点，则
2. 充分条件： 如果 则是的一个局部极小点。

若点满足一阶最优性条件(即), 则称是一个一阶稳定点。若该点处的海瑟矩阵不是半正定的, 那么不是一个局部极小点。进一步地, 如果海瑟矩阵既有正特征值又有负特征值, 我们称稳定点为一个鞍点。

注意, 二阶最优性条件给出的仍然是关于局部最优性的判断。对于给定点的全局最优性判断, 我们还需要借助实际问题的性质, 比如目标函数是凸的、非线性最小二乘问题中目标函数值为0等。特别地，由于凸问题的局部最优点总是全局最优的，因此是凸可微问题的最优点当且仅当一阶条件成立，即。

对偶理论

现在考虑一般的约束优化问题

其中为定义在或其子集上的实值函数, 和分别表示不等式约束(inequality)和等式约束(equality)对应的下标集合且各下标互不相同。上述问题的可行域为

通过将的示性函数加到目标函数中可以得到无约束优化问题。但是转化后问题的目标函数是不连续的、不可微的以及不是有限的, 这导致我们难以分析其理论性质以及设计有效的算法。

现在记

令为原问题的最优值。定义该问题的Lagrange函数为

定义该问题的Lagrange对偶函数为对关于变量去下界得到的

从定义出发可以直接得到如下重要结论：

Weak Dual Principle

如果，则

由于恒成立，两侧同时关于和取极大可以得到

称左侧优化问题

为原问题的Lagrange对偶问题 (Lagrangian dual problem)，记该对偶问题的最优值为，则是原问题的最优下界，称为相应的对偶间隙 (duality gap)。称中的元素为对偶可行解。

注意到对偶问题是一个最大化凹函数问题，因此无论原问题是否是凸优化问题，对应的Lagrange对偶问题总是一个凸优化问题。

Example. 考虑线性规划问题的对偶，原问题为

对应的Lagrange函数为

于是对偶函数为

所以最终的对偶问题为

令，于是上述问题等价于

借助共轭函数 考虑更一般的线性约束问题

它的对偶函数为

回忆的对偶函数为，因此

所以如果已知的共轭函数，则可以简化对偶函数的推导。

与弱对偶原则相对的是强对偶性：，不同于对任何问题都成立的弱对偶原则，强对偶性对于一般问题通常不成立，对凸问题也可能不成立，为了使强对偶性对于凸问题成立，需要添加额外的条件，称这些称保证凸问题强对偶性成立的条件为约束品性条件(constraint qualification condition)。

Remark. 一个问题不同等价形式的对偶可能差异巨大，当对偶问题难以推导或没有价值时, 可以尝试改写原问题的形式。常见的改写技巧包括：

1. 引入新变量与等式约束；
2. 将显式约束隐式化或将隐式约束显式化。

一般约束优化问题

我们下面讨论带约束优化问题的最优条件。和无约束优化问题类似，本节中，我们先讨论一阶必要条件，再讨论二阶条件。

切锥 给定可行域以及，若存在序列和正标量序列满足当时,
，并且以下极限存在

则称是在处的一个切向量。处的所有切向量的集合称为在处的切锥，记为。

不同约束类型下的切锥

对于一般的优化问题

我们有以下几何最优性条件：

几何最优性条件

设可行点是的一个局部极小点。如果与在处可微，则 上式等价于

不过上述几何刻画由极限定义，并不适用于一般计算。为此，我们定义线性化可行锥。

线性化可行锥 设，是非零向量。若存在使得

则称是可行域在处的一个可行方向。称处的积极集为

定义处的线性化可行方向锥为

线性化可行方向锥

不难证明，当一阶连续可微时，任意可行点处的线性化可行锥都包含切锥，即

不过切锥未必包含线性化可行锥，例如考虑

上述问题等价于

由于问题的可行域没有发生变化，故处切锥不变，均为，然而原问题在处的线性化可行锥为，而变换后的问题则有，因此，与原问题的线性化可行锥不一致，且此时有。

从上述例子中可以看出，线性化可行方向锥受可行域的代数表示形式的影响，而切锥仅有可行域本身决定，因此线性可行化方向锥容易计算, 但不能反映可行域的本质特征，而切锥能反映可行域的本质特征, 但不容易计算。为了解决这一矛盾，引入约束品性来沟通两者, 确保最优点处有，从而使用线性化可行方向锥来代替切锥。

线性无关约束品性 (LICQ) 给定可行点及相应的积极集。如果积极集对应的约束函数的梯度，即，是线性无关的，则称线性无关约束品性(LICQ)在点处成立。

可以证明，如果在某一可行点处线性无关约束品性(LICQ)成立，则处的切锥和线性化可行方向锥相等。

Mangasarian–Fromovitz约束品性 (MFCQ) 给定可行点及相应的积极集。如果存在使得

且等式约束对应的梯度线性无关，则称Mangasarian–Fromovitz约束品性在点处成立。

Mangasarian–Fromovitz约束品性是LICQ的的一个常用推广, 简称为MFCQ。LICQ可以推出MFCQ, 但是反过来不成立.在MFCQ成立的情况下, 我们也可以证明。

线性约束品性 若所有的约束函数都是线性的，则称线性约束品性成立。

当线性约束品性成立时，也有，因此对只含线性约束的优化问题, 例如线性规划、二次规划, 自然有$，我们无需再关注约束函数的梯度是否线性无关。一般来说, 线性约束品性和LICQ之间没有互相包含的关系。

KKT条件

之前给出的几何最优性条件为是的一个局部极小点当且仅当

当约束品性成立、线性化可行锥和切锥相等时, 上述条件可以变为

然而上式依然难以验证, 下面使用Farkas引理进行化简：

Farkas引理 设和是两个非负整数，给定中的、和，则满足

的不存在当且仅当存在和使得

由Farkas引理，取，以及，则时几何最优性条件等价于

其中

如果补充定义，令对于任意的都成立，则

这对应与Lagrange函数关于的一阶最优性条件。

另外，对于任意的，注意到

因此时乘子或者两种情况至少有一个成立，称该条件为互补松弛条件。当当两种情况恰好只有一种满足时, 我们也称严格互补松弛条件成立。

现在给出重要的KKT条件。

Karush-Kuhn-Tucker Conditions

设是一般优化问题 的一个局部最优点。如果线性化可行方向锥与切锥相同，即 则存在拉格朗日乘子使得如下KKT条件成立：

1. 稳定性条件：；
2. 原始等式可行性条件：；
3. 原始不等式可行性条件：；
4. 对偶可行性条件：；
5. 互补松弛条件：；

称满足上述KKT条件的变量对为KKT对，其中的称为KKT点。

Remark. 如果局部最优点处有，则不一定是KKT点。另外，KKT条件是局部最优点的必要条件，但不是充分条件。也就是说，KKT条件成立并不一定意味着是的一个局部极小点。

现在回到一般的优化问题

如果是满足KKT条件的点，在的情况下，对于任意的都有

此时一阶条件无法判断是否是最优值点，若，则需要利用二阶信息来进一步判断在其可行邻域内的目标函数值。事实上，Lagrange函数在这些方向上的曲率即可用来判断的最优性。我们首先先引入临界锥来精确刻画这些方向。

临界锥 设是满足KKT条件的KKT对，定义临界锥为

由定义可知临界锥是线性化可行方向锥的子集。沿着临界锥中的方向进行优化, 所有等式约束和对应的不等式约束(此时这些不等式均取等)都会尽量保持不变。当时，对于任意都有，因此

临界锥定义了依据一阶导数不能判断是否为下降或上升方向的线性化可行方向, 必须使用高阶导数信息加以判断。

现在给出一般优化问题的二阶最优性条件：

Second Order Optimal Conditions

1. 必要条件：设是问题的局部最优解，并且。令为相应的Lagrange乘子，是的KKT对，则
2. 充分条件：设在可行点处存在一个Lagrange乘子使得是的KKT对。如果 则是的一个严格局部最优解。

从上述定理中可以发现，与无约束优化问题的二阶最优性条件类似，约束优化问题的二阶最优性条件也要求某种“正定性”, 但只需要考虑临界锥中的向量而无需考虑全空间的向量。

带约束凸优化问题

一般地，带约束凸优化问题形如

其中是适当的凸函数，是的凸函数，已知。令

为关于的自然定义域，若，则令

定义可行域为

并且由于凸优化问题的可行域是凸集, 因此等式约束一般只能是线性约束。

凸优化问题有很多好的性质。一个自然的问题是:我们能否像研究无约束问题那样找到该问题最优解的一阶充要条件?如果这样的条件存在, 它在什么样的约束品性下成立? 在通常情况下, 优化问题的对偶间隙大于0, 即强对偶原理不满足，但对很多凸优化问题, 在特定约束品性下可以证明强对偶原理。直观的一种约束品性是存在满足所有约束条件的严格可行解。

首先给出集合的相对内点集的定义。给定集合, 记其仿射包为

称集合的相对内点集为

相对内点是内点的推广, 若本身的“维数”较低, 则不可能有内点, 但如果在它的仿射包中考虑, 则可能有相对内点。

Slater's Constraint Qualification Condition

若对凸优化问题 存在使得 则称对此问题Slater约束品性满足。该约束品性也称为 Slater条件。

Slater约束品性实际上是要求自然定义域的相对内点中存在使得不等式约束严格成立的点，时相对内点就是内点。

不等式约束是仿射函数时, Slater条件可以放宽。设前个不等式约束是仿射的, 此时Slater约束品性变为:存在, 满足

即对线性不等式约束无需要求其存在严格可行点。

Slater约束品性下的最优性条件有如下重要结论：

Strong Dual Principle

若凸优化问题满足Slater约束品性，则强对偶原理成立。

该定理表明，Slater条件成立时，当时, 对偶问题的最优解可以取到, 即存在对偶可行解使得

对于一般的约束优化问题, 当问题满足特定约束品性时, 我们知道KKT条件是局部最优解处的必要条件。而对于凸优化问题, 如果KKT条件成立, KKT条件则变为局部最优解的充要条件(根据凸性, 局部最优解也是全局最优解)。

First Order Condition for Convex Optimization

对于凸优化问题, 用表示矩阵的第列, 假设处Slater条件成立，那么和分别是原始, 对偶全局最优解当且仅当KKT条件成立，即

1. 稳定性条件：；
2. 原始等式可行性条件：；
3. 原始不等式可行性条件：；
4. 对偶可行性条件：；
5. 互补松弛条件：.

定理的充分性说明, 若能直接求解出凸优化问题的KKT对, 则其就是对应问题的最优解。实际上，除了Slater约束品性条件外，在前面第二小节中，我们知道LICQ、MFCQ条件也可以保证KKT条件成立。故任一约束品性条件成立时，KKT条件就是最优点的充分必要条件。当Slater条件不满足时, 即使原始问题存在全局极小值点, 也可能不存在满足KKT条件，例如

是一个凸问题，但是最优点并不满足KKT条件。

总结

无约束及非光滑优化问题的必要/充分条件

问题	一阶条件	二阶条件
可微问题	（必要）	（必要） （充分）
凸问题	（充要）	—
复合优化问题	（必要）	—
非凸非光滑问题	（必要）	—

带约束优化问题的必要/充分条件

问题	一阶条件	二阶条件	约束品性
一般问题	KKT 条件（必要）	（必要） （充分）	LICQ
凸优化问题	KKT 条件（充要）	—	任意约束品性条件

其中一般约束优化问题的二阶充分条件不需要LICQ为前提，并且约束品性也可以换为其他任意可以保证的约束品性。